.. _глава_81_start:

Диапазоны
==========

.. index::
    диапазон
    range

Диапазоны - это абстракция доступа к элементам. Эта абстракция позволяет использовать
различные алгоритмов над большим количеством типов контейнеров. Диапазоны
акцентируют внимание на том, как осуществляется доступ к элементам контейнера, а не на том, как
контейнер реализован.
Диапазоны - это очень простая концепция, которая основана на том, определяет ли тип
определенные наборы функций-членов. Мы уже встречались с этой концепцией в
foreach со структурами и классами (:ref:`foreach со структурами и классами<глава_73_start>`): любой тип, который предоставляет функции-члены
функции-члены empty, front и popFront(), может быть использован с циклом foreach
Набор этих трех функций-членов является требованием к диапазону
типа InputRange.
Знакомство с диапазонами я начну с InputRange, самого простого из всех типов диапазонов
Остальные диапазоны требуют больше функций-членов, чем InputRange.
Прежде чем продолжить, я хотел бы дать определения контейнеров и
алгоритмов.
*Контейнер (структура данных):* Контейнер - это очень полезная концепция, которая встречается
почти в каждой программе. Переменные собираются вместе с определенной целью и используются
вместе как элементы контейнера. Контейнерами в D являются его основные функции - массивы и
ассоциативные массивы, а также специальные типы контейнеров, которые определены в модуле
модуле std.container. Каждый контейнер реализуется как определенная структура данных.
Например, ассоциативные массивы - это реализация хэш-таблицы.
Каждая структура данных хранит свои элементы и предоставляет к ним доступ способами
которые характерны для этой структуры данных. Например, в структуре данных массива
элементы хранятся рядом друг с другом, а доступ к ним осуществляется по индексу элемента; в структуре данных связанного списка
списке элементы хранятся в узлах, и доступ к ним осуществляется путем перехода
через эти узлы один за другим; в структуре данных сортированного двоичного дерева узлы
обеспечивают доступ к предыдущим и последующим элементам через отдельные
ветви; и т. д.
В этой главе я буду использовать термины контейнер и структура данных
как взаимозаменяемые.
*Алгоритм (функция):* Обработка структур данных для конкретных целей
Обработка структур данных для конкретных целей определенными способами называется алгоритмом. Например, линейный поиск - это алгоритм, который
поиск осуществляется путем итерации по контейнеру от начала до конца; двоичный
бинарный поиск - это алгоритм, который ищет элемент, удаляя половину
кандидатов на каждом шаге; и т. д.
В этой главе я буду использовать термины "алгоритм" и "функция" как взаимозаменяемые.
В большинстве примеров, приведенных ниже, я буду использовать int в качестве типа элемента и int[] в качестве
тип контейнера. В действительности диапазоны более мощные, когда используются с
шаблонизированными контейнерами и алгоритмами. На самом деле, большинство контейнеров и
алгоритмов, которые связывают вместе диапазоны, являются шаблонами. Я оставлю примеры
шаблонизированных диапазонов до :ref:`следующей главы<chapter_82_start>`


История
-------

Очень удачной библиотекой, абстрагирующей алгоритмы и структуры данных друг от друга
является библиотека стандартных шаблонов (STL), которая также является частью стандартной библиотеки C++. 
STL обеспечивает эту абстракцию с помощью концепции итератора,
которая реализуется шаблонами C++.
Несмотря на то, что итераторы являются очень полезной абстракцией, у них есть некоторые
слабые стороны. Диапазоны D были разработаны для преодоления этих недостатков.
Андрей Александреску вводит диапазоны в своей работе "Об итерации " (???) и
демонстрирует, как они могут превосходить итераторы.


Диапазоны являются неотъемлемой частью D
----------------------------------------

В срезах D реализован самый мощный диапазон
RandomAccessRange, и в Phobos есть множество функций диапазона. Очень важно
понять, как диапазоны используются в Phobos.
Многие алгоритмы Phobos возвращают временные объекты диапазона. Например,
filter(), который выбирает элементы больше 10 в следующем коде,
на самом деле возвращает объект диапазона, а не массив:

.. code-block:: d

    import std.stdio;
    import std.algorithm;

    void main()
    {
        int[] values = [1, 20, 7, 11];
        writeln(values.filter!(value => value > 10));
    }

writeln лениво использует этот объект диапазона и обращается к элементам по мере необходимости:

.. code-block:: console

    [20, 11]

Этот вывод может навести на мысль, что filter() возвращает int[], но это не так.
Это видно из того, что следующее присваивание выдает ошибку
ошибку компиляции:

.. code-block:: d

    int[] chosen = values.filter!(value => value > 10); // ← ошибка компиляции

В сообщении об ошибке указывается тип объекта диапазон:

.. code-block:: console

    Error: cannot implicitly convert expression (filter(values))
    of type FilterResult!(__lambda2, int[]) to int[]

*Примечание: в используемой вами версии Phobos тип может быть другим.*
Можно преобразовать этот временный объект в настоящий массив, как мы увидим
позже в этой главе.

Традиционные реализации алгоритмов
----------------------------------

В традиционных реализациях алгоритмы знают, как реализованы структуры данных, с которыми они работают.
Например, следующая функция, печатающая элементы связанного списка, должна знать, что узлы этого списка
связного списка есть члены с именами element и next:

.. code-block:: d

    struct Node
    {
        int element;
        Node* next;
    }

    void print(const(Node)* list)
    {
        for (; list; list = list.next)
        {
            write(' ', list.element);
        }
    }

Аналогично, функция, печатающая элементы массива, должна знать, что массивы
имеют свойство длины, а доступ к их элементам осуществляется с помощью оператора []:

.. code-block:: d

    void print(const int[] array)
    {
        for (int i = 0; i != array.length; ++i)
        {
            write(' ', array[i]);
        }
    }

*Примечание: мы знаем, что функция foreach более полезна при итерации по массивам. В качестве
демонстрации того, как традиционные алгоритмы привязаны к структурам данных, давайте предположим.
что использование for оправдано.*
Привязка алгоритмов к структурам данных приводит к необходимости писать их
специально для каждого типа. Например, функции find(), sort(), swap() и т. д. должны быть
быть написаны отдельно для массива, связанного списка, ассоциативного массива, двоичного дерева, кучи и т. д.
В результате N алгоритмов, поддерживающих M структур данных, должны быть написаны NxM
раз. (Примечание: В действительности число меньше NxM, поскольку не каждый алгоритм
может быть применен к каждой структуре данных; например, ассоциативные массивы не могут быть сортированы
И наоборот, поскольку диапазоны абстрагируют алгоритмы от структур данных,
достаточно реализовать всего N алгоритмов и M структур данных. A
новая реализованная структура данных может работать со всеми существующими алгоритмами.
поддерживающими тот тип диапазона, который предоставляет новая структура данных, а вновь реализованный
реализованный алгоритм может работать со всеми существующими структурами данных, поддерживающими тип диапазона, 
который обеспечивает новая структура данных.

Диапазоны Фобоса
-----------------

Диапазоны, описанные в этой главе, отличаются от диапазонов чисел, которые записываются в
форме begin...end. Мы уже видели, как диапазоны чисел используются с циклом
циклом foreach и с фрагментами:

.. code-block:: d

    foreach (value; 3..7) { // number range,
    // NOT a Phobos range
    int[] slice = array[5..10]; // number range,
    // NOT a Phobos rang

Когда я пишу "диапазон" в этой главе, я имею в виду диапазон Фобоса.
Диапазоны образуют иерархию диапазонов. В самом низу этой иерархии находится простейший
диапазон InputRange. Остальные диапазоны предъявляют больше требований к диапазону
на котором они основаны. Ниже перечислены все диапазоны с их
требованиями, отсортированные от самых простых к более сложным:
∙InputRange: требует функций empty, front и popFront().
∙ForwardRange: дополнительно требует функцию save
∙BidirectionalRange: дополнительно требуется член back и popBack().
функции
∙RandomAccessRange: дополнительно требует оператора [] (и другого свойства, зависящего от того, является ли диапазон конечным)
в зависимости от того, является ли диапазон конечным или бесконечным)
Эту иерархию можно представить в виде следующего графика. RandomAccessRange имеет
конечную и бесконечную версии:

.. image:: images/81.4_1.png

График выше выполнен в стиле иерархий классов, где тип самого низкого уровня находится
на самом верху.
Эти диапазоны предназначены для обеспечения доступа к элементам. Есть еще один диапазон,
который связан с выводом элементов:
∙OutputRange: требует поддержки операции put(range, element).
Этих пяти типов диапазонов достаточно, чтобы абстрагировать алгоритмы от структур данных.


**Итерация путем сокращения диапазона**

Обычно итерация по элементам контейнера не изменяет сам
сам контейнер. Например, итерация по фрагменту с помощью foreach или for не
не влияет на фрагмент

.. code-block:: d

    int[] slice = [10, 11, 12];
    for (int i = 0; i != slice.length; ++i)
    {
        write(' ', slice[i]);
    }
    assert(slice.length == 3); // ← the length doesn't change


Другой способ итерации требует иного образа мышления: итерация может быть достигнута
достигается путем сокращения диапазона с самого начала. В этом методе всегда
первый элемент, который используется для доступа к элементу, извлекается,
чтобы перейти к следующему элементу

.. code-block:: d

    for (; slice.length; slice = slice[1 .. $])
    {
        write(' ', slice[0]); // ← always the first element
    }

Итерация осуществляется путем удаления первого элемента по выражению slice = slice[1..$]
выражением. Приведенный выше фрагмент полностью уничтожается, проходя через
следующие этапы:

.. code-block:: console

    [ 10, 11, 12 ]
        [ 11, 12 ]
            [ 12 ]
               [ ]


Концепция итераций "Фобоса" основана на этой новой идее
сокращении диапазона c начала. (Двунаправленный Range и конечный
RandomAccessRange можно сокращать и с конца.)
Обратите внимание, что приведенный выше код предназначен только для демонстрации этого типа итерации; не следует считать нормальной итерацией, 
как в этом примере.
Поскольку в большинстве случаев потеря элементов только для итерации по диапазону нежелательна.
то вместо этого можно использовать суррогатный диапазон. В следующем коде используется
отдельный фрагмент, чтобы сохранить элементы исходного:

.. code-block::

    int[] slice = [10, 11, 12];
    int[] surrogate = slice;
    for (; surrogate.length; surrogate = surrogate[1 .. $])
    {
        write(' ', surrogate[0]);
    }
    assert(surrogate.length == 0); // ← surrogate is consumed
    assert(slice.length == 3); // ← slice remains the same

Именно этот метод используется большинством функций диапазона Фобоса: они возвращают
специальные объекты диапазона, которые должны быть опустошены, чтобы сохранить оригинальные контейнеры.

InputRange
----------

Этот тип диапазона моделирует тип итерации, когда доступ к элементам осуществляется последовательно
как мы видели в функции print() выше. Большинство алгоритмов только
требуют, чтобы элементы итерировались в прямом направлении без необходимости
просматривать элементы, которые уже были пройдены. InputRange моделирует
стандартные входные потоки программ, где элементы удаляются из
из потока по мере их считывания.
Для полноты картины приведем три функции, которые требует InputRange:

* empty: определяет, является ли диапазон пустым; она должна возвращать true, если
  если диапазон пуст, и false в противном случае
* front: обеспечивает доступ к элементу в начале диапазона
* popFront(): сокращает диапазон с самого начала, удаляя первый элемент

*Примечание: я пишу empty и front без круглых скобок, так как их можно рассматривать как свойства диапазона; и popFront() со скобками, это функция с побочными эффектами.*
Вот как можно реализовать print() с помощью этих функций диапазона:

.. code-block:: d

    void print(T)(T range)
    {
        for (; !range.empty; range.popFront())
        {
            write(' ', range.front);
        }
        writeln();
    }

Также обратите внимание, что print() теперь является шаблоном функции, чтобы не ограничивать
print() теперь может работать с любым типом, который предоставляет три функции InputRange.
три функции InputRange.

**Пример InputRange**

Давайте переделаем тип School, который мы уже рассматривали, на этот раз в виде
InputRange. Мы можем представить School как контейнер Student, поэтому при проектировании в качестве
диапазона, его можно рассматривать как диапазон учеников.
Чтобы сделать пример коротким, опустим некоторые важные аспекты дизайна
аспекты. Давайте
* реализуем только те члены, которые имеют отношение к данному разделу
* оформляем все типы как структуры
* игнорируем спецификаторы и классификаторы, такие как private, public и const
* не используем преимущества контрактного программирования и модульного тестирования

.. code-block:: d

    import std.string;

    struct Student
    {
        string name;
        int number;
        string toString() const
        {
            return format("%s(%s)", name, number);
        }
    }

    struct School
    {
        Student[] students;
    }

    void main()
    {
        auto school = School([
            Student("Ebru", 1),
            Student("Derya", 2),
            Student("Damla", 3),
        ]);
    }

Чтобы School воспринималась как InputRange, мы должны определить три функции-члена  InputRange.
Чтобы функция empty возвращала true, когда диапазон пуст, мы можем использовать длину массива
массива students. Когда длина этого массива равна 0, диапазон считается
пустым:

.. code-block:: d

    struct School
    {
        // ...
        bool empty() const
        {
            return students.length == 0;
        }
    }

Для возврата первого элемента диапазона мы можем вернуть первый элемент
массива:

.. code-block:: d

    struct School
    {
        // ...
        ref Student front()
        {
            return students[0];
        }
    }

Примечание: я использовал ключевое слово ref, чтобы иметь возможность предоставить доступ к реальному элементу,
а не к его копии. В противном случае элементы были бы скопированы, посколькуStudent - это
struct.
Чтобы функция popFront() сократила диапазон с начала, мы можем сократить массив
массив students с самого начала:

.. code-block:: d

    struct School
    {
        // ...
        void popFront()
        {
            students = students[1 .. $];
        }
    }

*Примечание: Как я уже говорил выше, ненормально терять исходные элементы из
контейнера только для того, чтобы выполнить итерацию над ними. Мы решим эту проблему ниже, введя
специальный тип диапазона.*
Этих трех функций достаточно, чтобы использовать School в качестве
InputRange. В качестве примера добавим следующую строку в конец main()
выше, чтобы наш новый шаблон функции print() использовал school в качестве диапазона:

.. code-block:: d

    print(school);

print() использует этот объект в качестве InputRange и печатает его элементы на выходе:

.. code-block:: console

    Ebru(1) Derya(2) Damla(3)

Мы достигли цели - определили пользовательский тип как InputRange. Тип School фактически готов к
к использованию с алгоритмами Phobos или любой другой библиотеки, работающей с
типами InputRange. Примеры этого мы увидим ниже.


**Модуль std.array для использования фрагментов в качестве диапазонов**

Простой импорт модуля std.array делает самый распространенный контейнер способным использовать
самый распространенный тип диапазонов: фрагменты можно без проблем использовать как RandomAccessRange.
Модуль std.array предоставляет функции empty, front, popFront() и
другие функции диапазона для фрагментов. В результате готовы к использованию с любой
функцией диапазона, например, с функцией print():

.. code-block:: d

    import std.array;
    // ...
    print([ 1, 2, 3, 4 ])

*Примечание: При добавлении модуля std.range, который мы рассмотрим чуть ниже, модуль std.array
не нужно добавлять отдельно.*
Поскольку невозможно удалить элементы из массивов фиксированной длины
popFront() не может быть определен для них. Поэтому массивы фиксированной длины
сами по себе не могут быть использованы в качестве диапазонов:

.. code-block:: d

    void print(T)(T range)
    {
        for (; !range.empty; range.popFront())    { // ← ошибка компиляции
            write(' ', range.front);
        }
        writeln();
    }

    void main()
    {
        int[4] array = [1, 2, 3, 4];
        print(array);
    }

Было бы лучше, если бы ошибка компиляции появлялась в строке, где вызывается print()
вызывается. Это можно сделать, добавив ограничение шаблона к print(). Следующее
шаблонное ограничение использует преимущества isInputRange, которые мы рассмотрим в
следующей главе. С помощью шаблонного ограничения теперь ошибка компиляции будет
для строки, в которой вызывается print(), а не для строки, в которой определяется print():

.. code-block:: d

    void print(T)(T range) if (isInputRange!T)
    { // template constraint
        // ...
    }
    // ...
    print(array); // ← ошибка компиляции

К элементам массива фиксированной длины по-прежнему можно обращаться с помощью функций диапазона.
Для этого нужно использовать фрагмент всего массива, а не сам массив:

.. code-block:: d

    print(array[]); // теперь компилируется


Несмотря на то что фрагменты можно использовать в качестве диапазонов, не каждый тип диапазона может быть использован в качестве
массива. При необходимости все элементы можно скопировать в массив по одному.
std.array.array - вспомогательная функция, упрощающая эту задачу; array() выполняет итерацию по диапазонам
InputRange, копирует элементы и возвращает новый массив:

.. code-block:: d

    import std.array;
    // ...
    // Примечание: Также используется преимущество UFCS
    uto copiesOfStudents = school.array;
    writeln(copiesOfStudents);


.. code-block:: console

    Ebru(1), Derya(2), Damla(3)

Также обратите внимание на использование (:ref:`UFCS <глава_61_start>`)
UFCS очень хорошо сочетается с алгоритмами диапазонов, заставляя код естественным образом соответствовать порядку выполнения
выражений.

**Автоматическое декодирование строк как диапазонов dchar**

Будучи по определению символьными массивами, строки также можно использовать как диапазоны, просто
импортировав std.array. Однако строки char и wchar не могут быть использованы в качестве
RandomAccessRange.
std.array предоставляет специальную функциональность для всех типов строк: Итерация
над строками становится итерацией над кодовыми точками Юникода, а не над кодовыми единицами UTF.
В результате строки выглядят как диапазоны символов Юникода.
Следующие строки содержат ç и é, которые не могут быть представлены одним
и 𝔸 (математическая прописная буква A), которые не могут быть представлены одним символом.
одним символом (обратите внимание, что эти символы могут отображаться некорректно в той среде, в которой вы читаете эту главу).
среде, в которой вы читаете эту главу)

.. code-block:: d

    import std.array;
    // ...
    print("abcçdeé𝔸"c);
    print("abcçdeé𝔸"w);
    print("abcçdeé𝔸"d);

Программа выдает на выходе то, что мы обычно ожидаем от ряда букв:

.. code-block:: console

    a b c ç d e é 𝔸
    a b c ç d e é 𝔸
    a b c ç d e é 𝔸

Как видите, этот вывод не соответствует тому, что мы видели в главах "Символы" (стр.57) и Strings (стр. 75). В этих главах мы видели, что string - это
псевдоним для массива immutable(char), а wstring - псевдоним для массива
immutable(wchar). Соответственно, можно было бы ожидать увидеть в предыдущем выводе единицы кода UTF
вместо правильно декодированных символов Unicode.
Причина правильного отображения символов заключается в том, что при использовании в качестве
диапазонов, элементы строк автоматически декодируются. Как мы увидим ниже,
декодированные значения dchar - это не реальные элементы строк, а значения rvalues (стр. 181).
В качестве напоминания рассмотрим следующую функцию, которая рассматривает строки как
массивы кодовых единиц:

.. code-block:: d

    void printElements(T)(T str)
    {
        for (int i = 0; i != str.length; ++i)
        {
            write(' ', str[i]);
        }
        writeln();
    }
    // ...
    printElements("abcçdeé𝔸"c);
    printElements("abcçdeé𝔸"w);
    printElements("abcçdeé𝔸"d);

Когда доступ к символам осуществляется непосредственно с помощью индексации, элементы массивов не декодируются:

.. code-block:: console

    a b c � � d e � � � � � �
    a b c ç d e é ��� ���
    a b c ç d e é 𝔸

Автоматическое декодирование не всегда является желаемым поведением. Например.
следующая программа, которая пытается присвоить первый элемент строки, не может быть
не может быть скомпилирована, потому что возвращаемое значение .front является r-значением:

.. code-block:: d

    import std.array;
    void main()
    {
        char[] s = "hello".dup;
        s.front = 'H'; // ← ошибка компиляции
    }

.. code-block:: console

    Error: front(s) is not an lvalue

Когда алгоритму диапазона требуется изменить фактические кодовые единицы строки (и
когда это не приводит к нарушению кодировки UTF), то строка может быть использована
как диапазон элементов ubyte с помощью std.string.represention:

.. code-block:: d

    import std.array;
    import std.string;

    void main()
    {
        char[] s = "hello".dup;
        s.representation.front = 'H'; // compiles
        assert(s == "Hello");
    }

представление представляет фактические элементы строк char, wchar и dchar
как диапазоны ubyte, ushort и uint, соответственно.

**Диапазоны без фактических элементов**

Элементы объектов School на самом деле хранились в членах-членах students
slices. Таким образом, School.front возвращала ссылку на существующий объект Student.
Одна из возможностей диапазонов - гибкость, позволяющая не владеть элементами.
Front не обязательно должен возвращать реальный элемент реального контейнера. Возвращаемый
элемент может вычисляться каждый раз при вызове popFront() и использоваться
в качестве значения, возвращаемого front.
Выше мы уже рассматривали диапазон без фактических элементов: Поскольку char и
wchar не могут представлять все символы Юникода, символы Юникода, которые
которые появляются в качестве элементов диапазона, не могут быть реальными элементами какого-либо массива char или wchar.
В случае со строками front возвращает dchar, построенный из
соответствующих кодовых единиц UTF массивов:

.. code-block:: d

    import std.array;
    void main()
    {
        dchar letter = "é".front; // The dchar that is returned by
        // front is constructed from the
        // two chars that represent é
    }

Хотя тип элемента массива - char, возвращаемый тип front выше -
dchar. Этот dchar не является элементом массива, а представляет собой rvalue (стр. 181)
декодированное как символ Unicode из элементов массива.
Аналогично, некоторые диапазоны не имеют собственных элементов, но используются для предоставления
доступа к элементам других диапазонов. Это решение проблемы потери
элементов при итерации по объектам School выше. Для того чтобы сохранить
элементы реальных объектов School, можно использовать специальный InputRange.
Чтобы увидеть, как это делается, давайте определим новую структуру с именем StudentRange и
перенесем все функции-члены диапазона из School в эту новую структуру. Обратите внимание, что
School сама по себе больше не является диапазоном:

.. code-block::

    struct School
    {
        Student[] students;
    }

    struct StudentRange
    {
        Student[] students;
        this(School school)
        {
            this.students = school.students;
        }

        bool empty() const
        {
            return students.length == 0;
        }

        ref Student front()
        {
            return students[0];
        }

        void popFront()
        {
            students = students[1 .. $];
        }
    }

Новый диапазон начинается с фрагмента-члена, который предоставляет доступ к ученикам
School и потребляет этот фрагмент в popFront(). В результате фактический
фрагмент в School сохраняется:

.. code-block:: d

    auto school = School([
        Student("Ebru", 1),
        Student("Derya", 2),
        Student("Damla", 3)
    ]);
    print(StudentRange(school));
    // The actual array is now preserved:
    assert(school.students.length == 3);

*Примечание: Поскольку вся его работа передается его члену slice, StudentRange может не рассматриваться как
не может рассматриваться как хороший пример диапазона. На самом деле, если предположить, чтоstudents является доступным
член School, пользовательский код мог бы создать фрагмент School.students
непосредственно и использовать этот срез в качестве диапазона.*

**Бесконечные диапазоны**

Еще одним преимуществом того, что элементы не хранятся как действительные члены, является возможность создания
бесконечные диапазоны.
Сделать бесконечный диапазон так же просто, как заставить empty всегда возвращать false.
Поскольку empty является константой, ему даже не обязательно быть функцией, его можно определить как
значение перечисления:
enum empty = false; // ← бесконечный диапазон
Другой вариант - использовать неизменяемый статический член

.. code-block:: d

    static immutable empty = false;

В качестве примера давайте разработаем диапазон, представляющий ряд Фибоначчи.
Несмотря на наличие всего двух членов int, следующий диапазон может быть использован в качестве
бесконечный ряд Фибоначчи:

.. code-block:: d

    struct FibonacciSeries
    {
        int current = 0;
        int next = 1;
        enum empty = false; // ← infinite range
        int front() const
        {
            return current;
        }

        void popFront()
        {
            const nextNext = current + next;
            current = next;
            next = nextNext;
        }
    }

*Примечание: Хотя ряд бесконечен, поскольку его члены имеют типint, элементы этого ряда Фибоначчи будут неверны за пределами int.max.
Фибоначчи будут неправильными за пределами int.max.*
Поскольку для объектов FibonacciSeries значение empty всегда равно false, цикл for в функции
print() никогда не завершится для них:

.. code-block:: d

    print(FibonacciSeries()); // never terminates

Бесконечный диапазон полезен в тех случаях, когда не нужно полностью использовать диапазон
сразу же. Ниже мы рассмотрим, как использовать только некоторые элементы
FibonacciSeries ниже.

**Функции, возвращающие диапазоны**

Ранее мы создали объект StudentRange, явно написав
StudentRange(school).
В большинстве случаев вместо этого используется удобная функция, возвращающая объект такого диапазона
используется вместо нее. Например, функция, целью которой является возврат объекта
StudentRange, что упростило бы код:


.. code-block:: d

    StudentRange studentsOf(ref School school)
    {
        return StudentRange(school);
    }
    // ...
    // Note: Again, taking advantage of UFCS
    print(school.studentsOf);

Это удобнее, чем запоминать и прописывать имена типов диапазонов
типов, что на практике может оказаться довольно сложным.
Мы можем увидеть пример этого на примере простой функции std.range.take.
take() - это функция, которая предоставляет доступ к заданному количеству элементов
диапазона, начиная с самого начала. В действительности эта функциональность достигается не самой функцией
take(), а специальным объектом диапазона, который она возвращает. Этот факт не обязательно
не должен быть явным при использовании функции take()


.. code-block:: d

    import std.range;

    // ...
    auto school = School([
        Student("Ebru", 1),
        Student("Derya", 2),
        Student("Damla", 3)
    ]);
    print(school.studentsOf.take(2))

take() возвращает временный объект диапазона, который предоставляет доступ к первым
2 элементам school. В свою очередь, функция print() использует этот объект и выдает
следующий вывод:

.. code-block:: console

    Ebru(1) Derya(2)

Приведенные выше операции не вносят никаких изменений в школу; она по-прежнему состоит из 3
элементов:

.. code-block:: d

    print(school.studentsOf.take(2));
    assert(school.students.length == 3);

Конкретные типы объектов диапазона, которые возвращаются функциями типа take()
не важны. Иногда эти типы могут быть показаны в сообщениях об ошибках, или
мы можем вывести их сами с помощью функций typeof и stringof:

.. code-block:: d

    writeln(typeof(school.studentsOf.take(2)).stringof);

Согласно выводу, функция take() возвращает экземпляр шаблона с именем Take:

.. code-block:: console

    Take!(StudentRange)

.. index::
    std.range
    std.algorithm

**Модули std.range и std.algorithm**

Большим преимуществом определения наших типов как диапазонов является возможность использовать их не только
с нашими собственными функциями, но и с Phobos и другими библиотеками.
std.range включает в себя большое количество функций, структур и классов диапазонов.
std.algorithm включает множество алгоритмов, которые часто встречаются и в
стандартных библиотеках других языков.
Чтобы увидеть пример того, как наши типы могут использоваться со стандартными модулями, давайте
используем School с алгоритмом std.algorithm.swapFront. swapFront() меняет местами
передние элементы двух диапазонов InputRange. (Для этого требуется, чтобы передние элементы
двух диапазонов можно поменять местами. Массивы удовлетворяют этому условию.


.. code-block:: d

    import std.algorithm;

    // ...
    auto turkishSchool = School([
        Student("Ebru", 1),
        Student("Derya", 2),
        Student("Damla", 3)
    ]);
    auto americanSchool = School([Student("Mary", 10),
            Student("Jane", 20)]);
    swapFront(turkishSchool.studentsOf,
        americanSchool.studentsOf);
    print(turkishSchool.studentsOf);
    print(americanSchool.studentsOf);

The first elements of the two schools are swapped:

.. code-block:: console

    Mary(10) Derya(2) Damla(3)
    Ebru(1) Jane(20)

В качестве другого примера рассмотрим алгоритм std.algorithm.filter.
filter() возвращает специальный диапазон, который отфильтровывает элементы, не удовлетворяющие
определенному условию (предикату). Операция отсеивания элементов влияет только
влияет только на доступ к элементам; исходный диапазон сохраняется.
Предикаты - это выражения, которые должны иметь значение true для элементов, которые
удовлетворяют условию, и false для элементов, которые ему не удовлетворяют. Существует
существует несколько способов указать предикат, который должен использовать filter(). Как мы
как мы видели в предыдущих примерах, одним из способов является использование лямбда-выражения. На сайте
параметр a ниже представляет каждого студента:

.. code-block:: d

    school.studentsOf.filter!(a => a.number % 2)

Предикат выше выбирает элементы диапазона school.studentsOf, которые
имеют нечетные номера.
Как и take(), filter() также возвращает специальный объект диапазона. Этот объект диапазона
в свою очередь, можно передать другим функциям диапазона. Например, его можно передать в функцию
print():

Это выражение можно объяснить так: начните с диапазона school.studentsOf,
создать объект диапазона, который будет отфильтровывать элементы этого начального диапазона, и передать
новый объект диапазона в функцию print().
На выходе получаются студенты с нечетными номерами:

.. code-block:: console

    Ebru(1) Damla(3)

Если он возвращает true для элементов, удовлетворяющих условию, то
предикат также может быть задан в виде функции:

.. code-block:: d

    import std.array;

    // ...
    bool startsWithD(Student student)
    {
        return student.name.front == 'D';
    }

    print(school.studentsOf.filter!startsWithD);

Приведенная выше функция предиката возвращает true для студентов, чьи имена начинаются
с буквы D, и false для остальных.
Примечание:Использованиеstudent.name[0] означало бы первую единицу кода UTF-8, а не
первую букву. Как я уже говорил выше, front использует имя как диапазон и всегда возвращает
первый символ Юникода.
На этот раз выбраны и выведены ученики, чьи имена начинаются с буквы D:

.. code-block:: console

    Derya(2) Damla(3)

generate(), шаблон удобной функции из модуля std.range, позволяет
легко представить значения, возвращаемые функцией, как элементы
InputRange. Она принимает любую вызываемую сущность (указатель функции, делегат и т. д.) и
возвращает объект InputRange, концептуально состоящий из значений, которые
возвращаемых из этой вызываемой сущности.
Возвращаемый объект диапазона бесконечен. Каждый раз, когда происходит обращение к свойству front этого
объекта диапазона, вызывается исходная вызываемая сущность, чтобы получить новый элемент
из нее. Функция popFront() объекта range не выполняет никакой работы.
Например, следующий объект диапазона diceThrower можно использовать как бесконечный
диапазон:

.. code-block:: d

    import std.stdio;
    import std.range;
    import std.random;

    void main()
    {
        auto diceThrower = generate!(() => uniform(0, 6));
        writeln(diceThrower.take(10));
    }

.. code-block:: console

    [1, 0, 3, 5, 5, 1, 5, 1, 0, 4]

**Ленивость**

Еще одно преимущество функций, возвращающих объекты диапазона, заключается в том, что эти объекты можно
лениво использовать. Ленивые диапазоны создают свои элементы по одному и только тогда, когда это
когда это необходимо. Это может быть важно для скорости выполнения и потребления памяти.
Действительно, тот факт, что бесконечные диапазоны вообще могут существовать, стал возможен благодаря тому, что диапазоны
быть ленивыми.
Ленивые диапазоны создают свои элементы по одному и только тогда, когда это необходимо. Мы
видим пример этого на примере диапазона FibonacciSeries: Элементы
вычисляются функцией popFront() только по мере необходимости. Если бы FibonacciSeries был
нетерпеливым диапазоном и попытался бы произвести все элементы заранее, он никогда не смог бы закончиться
или найти место для элементов, которые он производит.
Другая проблема нетерпеливых диапазонов заключается в том, что им пришлось бы тратить время
и место для элементов, которые, возможно, никогда не будут использованы.
Как и большинство алгоритмов в Phobos, take() и filter() выигрывают от
лени. Например, мы можем передать FibonacciSeries в take() и заставить его
сгенерировать конечное число элементов:

.. code-block:: d

    print(FibonacciSeries().take(10));

Хотя FibonacciSeries бесконечна, вывод содержит только первые 10
чисел:

.. code-block:: console

    0 1 1 2 3 5 8 13 21 34

.. index::
    ForwardRange

ForwardRange
------------

InputRange моделирует диапазон, элементы которого выводятся из диапазона по мере их
итерации.
Некоторые диапазоны способны сохранять свои состояния, а также работать как
InputRange. Например, объекты FibonacciSeries могут сохранять свои состояния, потому что
эти объекты можно свободно копировать, и две копии продолжают свою жизнь
независимо друг от друга.
ForwardRange предоставляет функцию-член save, которая должна возвращать
копию диапазона. Копия, которую возвращает save, должна работать независимо от
объекта диапазона, из которого она была скопирована: итерации над одной копией не должны влиять на
на другую копию.
Импорт std.array автоматически превращает срезы в ForwardRange
диапазонами.
Чтобы реализовать сохранение для FibonacciSeries, мы можем просто вернуть копию
объекта:

.. code-block:: d

    struct FibonacciSeries
    {
        // ...
        FibonacciSeries save() const
        {
            return this;
        }
    }

Возвращенная копия представляет собой отдельный диапазон, который продолжается с того места, откуда
откуда она была скопирована.
Мы можем продемонстрировать, что скопированный объект не зависит от реального
диапазона с помощью следующей программы. Алгоритм std.range.popFrontN() в
следующем коде удаляет заданное количество элементов из указанного
диапазона:

.. code-block:: d

    import std.range;

    // ...
    void report(T)(const dchar[] title, const ref T range)
    {
        writefln("%40s: %s", title, range.take(5));
    }

    void main()
    {
        auto range = FibonacciSeries();
        report("Original range", range);
        range.popFrontN(2);
        report("After removing two elements", range);
        auto theCopy = range.save;
        report("The copy", theCopy);
        range.popFrontN(3);
        report("After removing three more elements", range);
        report("The copy", theCopy);
    }


.. code-block:: d

    Original range: [0, 1, 1, 2, 3]
    After removing two elements: [1, 2, 3, 5, 8]
    The copy: [1, 2, 3, 5, 8]
    After removing three more elements: [5, 8, 13, 21, 34]
    The copy: [1, 2, 3, 5, 8]

Также обратите внимание, что диапазон передается непосредственно в writefln функцию, которая находится в функции report(). Как и наша
print(), функции вывода модуля stdio могут принимать
объекты InputRange. В дальнейшем я буду использовать функции вывода stdio.
Алгоритм, который работает с ForwardRange, - это std.range.cycle. cycle()
перебирает элементы диапазона от начала до конца. На сайте
чтобы иметь возможность начать с самого начала, он должен иметь возможность сохранить копию
начального состояния диапазона, поэтому ему требуется ForwardRange.
Поскольку FibonacciSeries теперь является ForwardRange, мы можем попробовать цикл() с объектом
объектом FibonacciSeries; но для того, чтобы избежать итерации cycle() по
бесконечный диапазон и, как следствие, никогда не находил его конца, мы должны сначала создать конечный
диапазон, передав FibonacciSeries через take():

.. code-block:: d

    writeln(FibonacciSeries().take(5).cycle.take(20));

Чтобы сделать результирующий диапазон конечным, диапазон, возвращаемый функцией
cycle, также передается через take(). Результат состоит из первых двадцати
элементов цикла через первые пять элементовFibonacciSeries:

.. code-block:: console

    [0, 1, 1, 2, 3, 0, 1, 1, 2, 3, 0, 1, 1, 2, 3, 0, 1, 1, 2, 3]

Мы могли бы определить и промежуточные переменные. Ниже приведен
эквивалент приведенного выше однострочного кода:

.. code-block:: d

    auto series                   = FibonacciSeries();
    auto firstPart                = series.take(5);
    auto cycledThrough            = firstPart.cycle;
    auto firstPartOfCycledThrough = cycledThrough.take(20);
    writeln(firstPartOfCycledThrough);

Я хотел бы еще раз обратить внимание на важность лени: Первые четыре
строк выше просто строят объекты диапазона, которые в конечном итоге создадут
элементы. Числа, входящие в результат, вычисляются с помощью функции
FibonacciSeries.popFront() по мере необходимости.

*Примечание: хотя мы начали работу сFibonacciSeries как сForwardRange, мы
на самом деле мы передали результатFibonacciSeries().take(5) вcycle().
Функция take() является адаптивной: диапазон, который она возвращает, будет aForwardRange, если ее параметр - это
ForwardRange. Как это достигается с помощью функцииisForwardRange, мы увидим в
следующей главе.*

.. index::
    BidirectionalRange

BidirectionalRange
-------------------

BidirectionalRange предоставляет две функции-члена поверх функций-членов
функции ForwardRange. back аналогична front: она предоставляет доступ к последнему
элементу диапазона. popBack() аналогична popFront(): она удаляет последний
элемент из диапазона.
Импорт std.array автоматически превращает срезы в
BidirectionalRange.
Хорошим примером BidirectionalRange является функция std.range.retro.
retro() берет BidirectionalRange и связывает его переднюю и заднюю части, а также
popFront() к popBack(). В результате исходный диапазон итерируется в
обратном порядке:


.. code-block:: d

    writeln([ 1, 2, 3 ].retro)

.. code-block:: console

    [3, 2, 1]

Давайте определим диапазон, который ведет себя аналогично специальному диапазону, который возвращает retro()
возвращает. Хотя следующий диапазон имеет ограниченную функциональность, он показывает, насколько
насколько мощными могут быть диапазоны:

.. code-block:: d

    import std.array;
    import std.stdio;

    struct Reversed
    {
        int[] range;
        this(int[] range)
        {
            this.range = range;
        }

        bool empty() const
        {
            return range.empty;
        }

        int front() const
        {
            return range.back; // ← reverse
        }

        int back() const
        {
            return range.front; // ← reverse
        }

        void popFront()
        {
            range.popBack(); // ← reverse
        }

        void popBack()
        {
            range.popFront(); // ← reverse
        }
    }

    void main()
    {
        writeln(Reversed([1, 2, 3]));
    }

Вывод такой же, как и у retro():

.. code-block:: console

    [3, 2, 1]

.. index::
    RandomAccessRange

RandomAccessRange
------------------

RandomAccessRange представляет диапазоны, которые позволяют получать доступ к элементам с помощью оператора []
оператора. Как мы уже видели в главе "Перегрузка операторов" (стр. 298), оператор []
определяется функцией-членом opIndex().
Импорт модуля std.array заставляет фрагменты становиться RandomAccessRange
диапазонами, только если это возможно. Например, поскольку кодировки UTF-8 и UTF-16 не
не позволяют обращаться к символам Юникода по индексу, массивы char и wchar не могут
использоваться в качестве диапазонов RandomAccessRange для символов Юникода. С другой стороны,
поскольку коды кодировки UTF-32 один к одному соответствуют кодам символов Юникода
кодам символов, массивы dchar можно использовать в качестве диапазонов RandomAccessRange для символов Юникода.
символов Юникода.
Естественно, что каждый тип определяет функцию-член opIndex()
в соответствии со своей функциональностью. Однако компьютерная наука предъявляет определенные требования к
алгоритмической сложности: случайный доступ должен занимать постоянное время. Постоянное время
доступа означает, что время, затрачиваемое на обращение к элементу, не зависит от
количества элементов в контейнере. Поэтому, независимо от того, насколько велик
диапазон, доступ к элементу не должен зависеть от длины диапазона.
Для того чтобы считаться RandomAccessRange, должно выполняться одно из следующих
условий:
* быть бесконечным ForwardRange
или
* быть двунаправленным диапазоном, который также обеспечивает свойство длины.
В зависимости от того, какое условие выполнено, диапазон является либо бесконечным, либо конечным.

**Бесконечный RandomAccessRange**

Ниже перечислены все требования к RandomAccessRange, который основан
на бесконечном диапазоне (InfiniteForwardRange):
* empty, front и popFront(), которые требует InputRange
* save, что требует ForwardRange
* opIndex(), который требует RandomAccessRange
* значение empty должно быть известно во время компиляции как false
Мы смогли определить FibonacciSeries как ForwardRange. Однако,
opIndex() не может быть реализован для работы в постоянное время для
FibonacciSeries, потому что для доступа к элементу требуется сначала получить доступ ко всем
предыдущих элементов.
В качестве примера, где opIndex() может работать в постоянном времени, давайте определим
бесконечный диапазон, состоящий из квадратов целых чисел. Хотя следующий диапазон будет
бесконечным, доступ к любому из его элементов может происходить в постоянное время:

.. code-block:: d

    class SquaresRange
    {
        int first;
        this(int first = 0)
        {
            this.first = first;
        }

        enum empty = false;
        int front() const
        {
            return opIndex(0);
        }

        void popFront()
        {
            ++first;
        }

        SquaresRange save() const
        {
            return new SquaresRange(first);
        }

        int opIndex(size_t index) const
        {
            /* This function operates at constant time */
            immutable integerValue = first + cast(int) index;
            return integerValue * integerValue;
        }
    }

*Примечание:Логичнее было бы определитьSquaresRange как struct.*

Хотя для элементов этого диапазона не было выделено места, к их
к элементам можно обратиться с помощью оператора []:

.. code-block:: d

    auto squares = new SquaresRange();
    writeln(squares[5]);
    writeln(squares[10]);

Результат содержит элементы с индексами 5 и 10:

.. code-block:: console

    25
    100

Элемент с индексом 0 всегда должен представлять собой первый элемент диапазона.
Мы можем воспользоваться функцией popFrontN(), чтобы проверить, так ли это на самом деле
так ли это:

.. code-block:: d

    squares.popFrontN(5);
    writeln(squares[0])

Первые 5 элементов диапазона - 0, 1, 4, 9 и 16; квадраты 0, 1, 2, 3 и 4.
После их удаления квадрат следующего значения становится первым элементом
диапазона:

.. code-block:: console

    25

Будучи RandomAccessRange (наиболее функциональным диапазоном), SquaresRange может также
использоваться в качестве других типов диапазонов. Например, в качестве InputRange при передаче в
filter():

.. code-block:: d

    bool are_lastTwoDigitsSame(int value)
    {
        /* Must have at least two digits */
        if (value < 10)
        {
            return false;
        }
        /* Last two digits must be divisible by 11 */
        immutable lastTwoDigits = value % 100;
        return (lastTwoDigits % 11) == 0;
    }

    writeln(squares.take(50).filter!are_lastTwoDigitsSame);

Результат состоит из элементов из первых 50, где последние две цифры одинаковы
одинаковые:

.. code-block:: console

    [100, 144, 400, 900, 1444, 1600]

**Конечный RandomAccessRange**

Ниже перечислены все требования к RandomAccessRange, который основан
на конечном двунаправленном диапазоне (finiteBidirectionalRange):
* empty, front и popFront(), которые требует InputRange
* save, что требует ForwardRange
* back и popBack(), что требует BidirectionalRange
* opIndex(), который требует RandomAccessRange
* length, которая обеспечивает длину диапазона.
В качестве примера конечного RandomAccessRange определим диапазон, который работает
аналогично std.range.chain. chain() представляет элементы нескольких
отдельных диапазонов так, как будто они являются элементами одного большого диапазона. Хотя chain()
работает с любым типом элемента и любым типом диапазона, чтобы не затягивать пример,
давайте реализуем диапазон, который работает только с кусочками int.
Назовем этот диапазон Together и будем ожидать от него следующего поведения:

.. code-block:: d

    auto range = Together([ 1, 2, 3 ], [ 101, 102, 103]);
    writeln(range[4]);

При построении с двумя отдельными массивами, приведенными выше, range должен представить все
все эти элементы как один диапазон. Например, хотя ни в одном из массивов нет элемента
элемент с индексом 4, элементом 102 должен быть элемент, соответствующий
индексу 4 коллективного диапазона:

.. code-block:: console

    102

Как и ожидалось, печать всего диапазона должна содержать все элементы:

.. code-block::

    writeln(range);

Выходные данные:

.. code-block:: console

    [1, 2, 3, 101, 102, 103]

Вместе будет работать лениво: элементы не будут копироваться в новый больший
массив; доступ к ним будет осуществляться из исходных фрагментов.

Мы можем воспользоваться преимуществами вариативных функций, которые были представлены в главе
Глава "Переменное число параметров" (стр. 258), чтобы инициализировать диапазон любым
количеством исходных фрагментов:

.. code-block:: d

    struct Together
    {
        const(int)[][] slices;
        this(const(int)[][] slices...)
        {
            this.slices = slices.dup;
            clearFront();
            clearBack();
        }
        // ...
    }

Обратите внимание, что тип элемента - const(int), что указывает на то, что эта структура не будет
модифицировать элементы диапазонов. Однако фрагменты обязательно будут модифицированы функцией
popFront() для реализации итерации.
Вызовы clearFront() и clearBack(), которые выполняет конструктор, предназначены для того, чтобы
удалить пустые фрагменты из начала и конца исходных фрагментов. Такие
пустые фрагменты не меняют поведение Together, и их удаление перед
и их удаление упростит реализацию:

.. code-block:: d

    struct Together
    {
        // ...
        private void clearFront()
        {
            while (!slices.empty && slices.front.empty)
            {
                slices.popFront();
            }
        }

        private void clearBack()
        {
            while (!slices.empty && slices.back.empty)
            {
                slices.popBack();
            }
        }
    }

Позже мы будем вызывать эти функции из popFront() и popBack().
Поскольку функции clearFront() и clearBack() удаляют все пустые фрагменты из
начала и конца, наличие фрагмента означает, что коллективный диапазон
еще не пуст. Другими словами, диапазон следует считать пустым только в том случае, если
не осталось ни одного кусочка:

.. code-block:: d

    struct Together
    {
        // ...
        bool empty() const
        {
            return slices.empty;
        }
    }

Первый элемент первого фрагмента является первым элементом диапазона Together:

.. code-block:: d

    struct Together
    {
        // ...
        int front() const
        {
            return slices.front.front;
        }
    }

Удаление первого элемента первого фрагмента удаляет и первый элемент этого диапазона
также. Поскольку в результате этой операции первая долька может остаться пустой, мы должны вызвать функцию
clearFront(), чтобы удалить этот пустой фрагмент и те, что находятся после него:

.. code-block:: d

    struct Together
    {
        // ...
        void popFront()
        {
            slices.front.popFront();
            clearFront();
        }
    }

Копия этого диапазона может быть построена из копии члена slices:

.. code-block:: d

    struct Together
    {
        // ...
        Together save() const
        {
            return Together(slices.dup);
        }
    }

*Обратите внимание, что в этом случае.dup копирует только фрагменты, а не элементы фрагмента, которые он содержит.
содержит.*
Операции в конце диапазона аналогичны операциям в начале:

.. code-block:: d

    struct Together
    {
        // ...
        int back() const
        {
            return slices.back.back;
        }

        void popBack()
        {
            slices.back.popBack();
            clearBack();
        }
    }

Длина диапазона может быть рассчитана как сумма длин срезов:

.. code-block:: d

    struct Together
    {
        // ...
        size_t length() const
        {
            size_t totalLength = 0;
            foreach (slice; slices)
            {
                totalLength += slice.length;
            }
            return totalLength;
        }
    }

В качестве альтернативы длину можно вычислить с меньшим количеством кода, воспользовавшись преимуществами
std.algorithm.fold. fold() принимает операцию в качестве параметра шаблона и
применяет эту операцию ко всем элементам диапазона:

.. code-block:: d

    import std.algorithm;

    // ...
    size_t length() const
    {
        return slices.fold!((a, b) => a + b.length)(size_t.init);
    }

Параметр a в шаблоне представляет текущий результат (в данном случае сумму), а b - текущий элемент.
Первый параметр функции - это
диапазон, содержащий элементы, а второй параметр функции - начальное
значение результата (size_t.init равен 0). (Обратите внимание, как slices записывается перед fold
используя преимущества UFCS (стр. 385)).
*Примечание: Кроме того, вместо того, чтобы вычислять длину каждый раз, когда вызывается функция length, можно
может быть ощутимо быстрее поддерживать переменную-член, возможно, с именем length_,
которая всегда равна правильной длине коллективного диапазона. Этот член может быть
вычисляться один раз в конструкторе и соответствующим образом корректироваться по мере удаления элементов функциями
popFront() иpopBack().*
Один из способов вернуть элемент, соответствующий определенному индексу, заключается в том, чтобы просмотреть
в каждом срезе, чтобы определить, будет ли этот элемент среди элементов
этого среза:

.. code-block:: d

    struct Together
    {
        // ...
        int opIndex(size_t index) const
        {
            /* Save the index for the error message */
            immutable originalIndex = index;
            foreach (slice; slices)
            {
                if (slice.length > index)
                {
                    return slice[index];
                }
                else
                {
                    index -= slice.length;
                }
            }
            throw new Exception(
                format("Invalid index: %s (length: %s)",
                    originalIndex, this.length));
        }
    }

Примечание:ThisopIndex() не удовлетворяет требованию постоянного времени, о котором говорилось выше.
упоминалось выше. Чтобы эта реализация была приемлемо быстрой, член slices
не должен быть слишком длинным.
Теперь этот новый диапазон готов к использованию с любым количеством срезов int. С
помощью функций take() и array() мы можем даже включить типы диапазонов, которые мы определили ранее в этой главе: take() и array().
определенные ранее в этой главе:

.. code-block:: d

    auto range = Together(FibonacciSeries().take(10).array,
                          [ 777, 888 ],
                          (new SquaresRange()).take(5).array);
    writeln(range.save);

Доступ к элементам трех срезов осуществляется так, как если бы они были элементами одного
большого массива:

.. code-block:: console

    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 777, 888, 0, 1, 4, 9, 16]

Мы можем передать этот диапазон другим алгоритмам работы с диапазонами. Например, в retro(), который
требуется BidirectionalRange:

.. code-block:: d

    writeln(range.save.retro);

Вывод:

.. code-block:: console

    [16, 9, 4, 1, 0, 888, 777, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0]

Разумеется, вам следует использовать более функциональный std.range.chain вместо  Together в ваших программах.

.. index::
    OutputRange

OutputRange
----------------

Все типы диапазонов, которые мы рассматривали до сих пор, связаны с доступом к элементам.
OutputRange представляет потоковый вывод элементов, подобно отправке символов
в stdout.
Ранее я уже упоминал, что OutputRange требует поддержки операции
put(range, element). put() - это функция, определенная в модуле std.range
модуля. Она определяет возможности диапазона и элемента во время компиляции
и использует наиболее подходящий метод для вывода элемента.
put() рассматривает следующие случаи в том порядке, в котором они перечислены ниже, и
применяет метод для первого подходящего случая. R представляет тип диапазона;
range - объект диапазона; E - тип элемента; e - элемент диапазона:


.. list-table:: Права доступа
   :widths: 50 50
   :header-rows: 1
   :align: center

   * - Case Considered
     - Method Applied
   * - R has a member function named put and put can take an E as argument
     - range.put(e);
   * - R has a member function named put and put can take an E[] as argumen
     - range.put([ e ])
   * - R is an InputRange and e can be assigned to range.front
     - range.front = e; range.popFront();
   * - E is an InputRange and can be copied to R
     - or (; !e.empty; e.popFront()) put(range, e.front);
   * - R can take E as argument (e.g. R could be a delegate)
     - range(e);
   * - R can take E[] as argument (e.g. R could be a delegate)
     - range([ e ]);

Давайте определим диапазон, соответствующий первому случаю: У диапазона будет член
функция put(), которая принимает параметр, соответствующий типу OutputRange.
Этот диапазон вывода будет использоваться для вывода элементов в несколько файлов,
включая stdout. Когда элементы выводятся с помощью put(), все они будут
записываться во все эти файлы. В качестве дополнительной функциональности добавим возможность
указывать разделитель, который будет записываться после каждого элемента.

.. code-block:: d

    struct MultiFile
    {
        string delimiter;
        File[] files;
        this(string delimiter, string[] fileNames...)
        {
            this.delimiter = delimiter;
            /* stdout is always included */
            this.files ~= stdout;
            /* A File object for each file name */
            foreach (fileName; fileNames)
            {
                this.files ~= File(fileName, "w");
            }
        }
        // This is the version that takes arrays (but not strings)
        void put(T)(T slice) if (isArray!T && !isSomeString!T)
        {
            foreach (element; slice)
            {
                // Note that this is a call to the other version
                // of put() below
                put(element);
            }
        }
        // This is the version that takes non-arrays and strings
        void put(T)(T value) if (!isArray!T || isSomeString!T)
        {
            foreach (file; files)
            {
                file.write(value, delimiter);
            }
        }
    }

Чтобы использовать диапазон вывода элементов любого типа, put() также
шаблонизируется по типу элемента.
Алгоритм в Phobos, использующий OutputRange, - это std.algorithm.copy.
copy() - это очень простой алгоритм, который копирует элементы InputRange
в OutputRange.

.. code-block::

    import std.traits;
    import std.stdio;
    import std.algorithm;

    // ...
    void main()
    {
        auto output = MultiFile("\n", "output_0", "output_1");
        copy([1, 2, 3], output);
        copy(["red", "blue", "green"], output);
    }

blueЭтот код выводит элементы входных диапазонов как в stdout, так и в файлы
с именами "output_0" и "output_1":

.. code-block:: console

    1
    2
    3
    red
    blue
    green

**Использование фрагментов в качестве OutputRange**

Модуль std.range также делает срезы объектами OutputRange. (Для сравнения,
std.array делает их только входными диапазонами.) К сожалению, использование фрагментов в качестве
OutputRange приводит к непонятному эффекту: фрагменты теряют элемент при каждой операции put()
и этим элементом является элемент, который только что был выведен!
Причина такого поведения кроется в том, что у срезов нет функции-члена put()
функции-члена. В результате третий случай из предыдущей таблицы выполняется для
slices и применяется следующий метод:

.. code-block:: d

    range.front = e;
    range.popFront();

По мере выполнения приведенного выше кода для каждого put() передний элемент фрагмента
присваивается значение выводимого элемента, который впоследствии будет удален из
из среза с помощью функции popFront():

.. code-block:: d

    import std.stdio;
    import std.range;

    void main()
    {
        int[] slice = [1, 2, 3];
        put(slice, 100);
        writeln(slice);
    }

В результате, хотя фрагмент и используется как OutputRange, он, как ни странно, теряет
элементы:
[2, 3]
Чтобы избежать этого, в качестве OutputRange следует использовать отдельный фрагмент:

.. code-block:: d

    import std.stdio;
    import std.range;

    void main()
    {
        int[] slice = [1, 2, 3];
        int[] slice2 = slice;
        put(slice2, 100);
        writeln(slice2);
        writeln(slice);
    }

На этот раз потребляется второй фрагмент, а исходный фрагмент содержит ожидаемые
элементы:
[2, 3]
[100, 2, 3] ← ожидаемый результат
Еще одним важным фактом является то, что длина фрагмента не увеличивается при использовании его в качестве
OutputRange. Ответственность программиста заключается в том, чтобы обеспечить
чтобы в срезе было достаточно памяти:

.. code-block:: d

    int[] slice = [1, 2, 3];
    int[] slice2 = slice;
    foreach (i; 0 .. 4)
    { // ← no room for 4 elements
        put(slice2, i * 100);
    }

Когда фрагмент становится полностью пустым из-за косвенных вызовов popFront()
программа завершается с исключением:

.. code-block:: console

    core.exception.AssertError@...: Attempting to fetch the front of an empty array of int

std.array.Appender и его удобная функция appender позволяют использовать фрагменты
в качествеOutputRange, куда добавляются элементы. Функция put() специального объекта
специального объекта range, который возвращает appender(), фактически добавляет элементы к
исходному фрагменту:

.. code-block:: d

    import std.array;

    // ...
    auto a = appender([1, 2, 3]);
    foreach (i; 0 .. 4)
    {
        a.put(i * 100);
    }

В приведенном выше коде appender вызывается с массивом и возвращает специальный объект range
объект. Этот объект диапазона, в свою очередь, используется в качестве OutputRange путем вызова его функции put()
функции-члена. Доступ к результирующим элементам осуществляется через его свойство .data:
writeln(a.data);

.. code-block:: d

    writeln(a.data);

Вывод:

.. code-block:: console

    [1, 2, 3, 0, 100, 200, 300]

Appender также поддерживает оператор ~=:

.. code-block:: d

    a ~= 1000;
    writeln(a.data);

Вывод:

.. code-block:: console

    [1, 2, 3, 0, 100, 200, 300, 1000]

**toString() с параметром OutputRange**

Аналогично тому, как функции-члены toString можно определить как принимающие делегатский
(стр. ???), можно определить функцию, принимающую параметр OutputRange.
Такие функции, как format, writefln и writeln, работают более эффективно, поскольку
помещая выводимые символы прямо в выходной буфер диапазона вывода.
Чтобы иметь возможность работать с любым типом OutputRange, такие определения toString должны
должны быть шаблонами функций, опционально с ограничениями шаблона:

.. code-block:: d

    import std.stdio;
    import std.range;

    struct S
    {
        void toString(O)(ref O o) const
        if (isOutputRange!(O, char))
        {
            put(o, "hello");
        }
    }

    void main()
    {
        auto s = S();
        writeln(s);
    }

Обратите внимание, что код внутри main() не определяет объект OutputRange. Этот объект
объект определяется командой writeln для хранения символов перед их печатью:

.. code-block:: console

    hello

Шаблоны диапазонов
------------------

Хотя в этой главе мы использовали в основном диапазоны int, диапазоны и алгоритмы диапазонов
гораздо полезнее, когда они определены в виде шаблонов.
Модуль std.range включает в себя множество шаблонов диапазонов. Мы познакомимся с этими
шаблоны в следующей главе.

Резюме
-------

* Диапазоны абстрагируют структуры данных от алгоритмов и позволяют использовать их с алгоритмами беспрепятственно.
* Диапазоны - это концепция D и основа многих возможностей Phobos.
* Многие алгоритмы Phobos возвращают ленивые объекты диапазонов для выполнения своих специальных задач.
  задач.
* UFCS хорошо работает с алгоритмами диапазонов.
* При использовании в качестве объектов InputRange элементы строк являются символами Unicode
  символы.
* InputRange требует empty, front и popFront().
* Для ForwardRange дополнительно требуется save.
* BidirectionalRange дополнительно требует back и popBack().
* Infinite RandomAccessRange требует opIndex() над ForwardRange.
* Finite RandomAccessRange требует opIndex() и length по сравнению с
  BidirectionalRange.
* std.array.appender возвращает OutputRange, который добавляет к срезам.
* Ломтики - это диапазоны конечного RandomAccessRange
* Массивы фиксированной длины не являются диапазонами.
